摘要 :
Many problems in computer applications can in theory be solved by searching through a directed-acyclic graph (DAG). In practice, however, this approach has been hampered by our analytical inability to predict the search cost accur...
展开
Many problems in computer applications can in theory be solved by searching through a directed-acyclic graph (DAG). In practice, however, this approach has been hampered by our analytical inability to predict the search cost accurately without actually implementing and executing the program. To overcome this inability, a simple and quick heuristic procedure based on a stratified sampling approach is presented. It generalizes a tree sampling technique already shown to be useful in predicting the performance of tree-searching programs. With the addition of this DAG sampling procedure, we should be able to forecast the complexity and feasibility of alternative tree or DAG searching algorithms so that we may utilize our computational resources more effectively.
收起
摘要 :
An algorithm is described for the symmetric traveling salesman problem (TSP)based on a bipartite two-matching lower bounding technique. The lower bound is strengthened by using the bipartite two-matching as the basis for a heurist...
展开
An algorithm is described for the symmetric traveling salesman problem (TSP)based on a bipartite two-matching lower bounding technique. The lower bound is strengthened by using the bipartite two-matching as the basis for a heuristic algorithm for the dual of integer two-matching.. We use this dual as a lower bound for the symmetric traveling salesman problem in a branch and bound algorithm. Results are presented for random symmetric TSPs with up to 3000 cities. On Euclidean problems the two-matching bound is weaker than on random problems and algorithm performance deteriorates as a result. The algorithm successfully solves 11 of 15 Euclidean problems from the literature with sizes ranging from 17 to 99 cities.
收起
摘要 :
In connection with large rule bases and real-time processing of information, parallel expert systems form an important field of research. In an agenda-driven expert system, both forward and backward reasoning may occur, depending ...
展开
In connection with large rule bases and real-time processing of information, parallel expert systems form an important field of research. In an agenda-driven expert system, both forward and backward reasoning may occur, depending on the strategy. Still, it may happen that irrelevant parts of the search space are searched (staggering effects). Seemingly attractive possibilities, so-called phantoms, give rise to the effect. In order to discover and fight phantoms, a ghostbusting strategy is introduced. In HYDRA (Hypothesis Deduction through Rule Application) forward and backward reasoning can be combined thanks to a well-chosen priority function. In the paper, conventional search techniques, supported by the above-mentioned strategies, are compared with reference to some results. These results turn out not to be substantially improved by the addition of a common heuristic.
收起
摘要 :
In the paper a model for heuristic reasoning with uncertain knowledge is presented. The model is a generalization of the approach proposed by Clancey (Cla-84, Cla-85). The author offers a clear semantics for the model, showing tha...
展开
In the paper a model for heuristic reasoning with uncertain knowledge is presented. The model is a generalization of the approach proposed by Clancey (Cla-84, Cla-85). The author offers a clear semantics for the model, showing that the heuristic reasoning process can be given a clear probabilistic interpretation. (Copyright (c) 1988 by Faculty of Technical Mathematics and Informatics, Delft, The Netherlands.)
收起
摘要 :
An embedded network within a linear program is, roughly speaking, a subset of constraints that represent conservation of flow. In this paper, we examine three broad classes of heuristic techniques-row-scanning deletion, column sca...
展开
An embedded network within a linear program is, roughly speaking, a subset of constraints that represent conservation of flow. In this paper, we examine three broad classes of heuristic techniques-row-scanning deletion, column scanning deletion, and row-scanning addition-for the extraction of large embedded networks. We describe a variety of implementations, and compare their performance on varied test problems. The success of our tests depends, in part, on several preprocessing steps that scale the constraint matrix and that set aside certain rows and columns. Efficiency of the subsequent network extraction is dependent on the implementation, in predictable ways. Effectiveness is harder to explain; the more sophisticated and expensive implementations seem to be more reliable, but much simpler implementations sometimes find equally large networks. The largest networks are obtained by applying a final augmentation phase, which is studied in the second part of this paper.
收起
摘要 :
Novick and Lindley (1978, 1979) have dealt with the use of utility functions for applications in education and have advocated the use of the standard gamble (von Neumann and Morgenstern, 1953) elicitation procedure with the additi...
展开
Novick and Lindley (1978, 1979) have dealt with the use of utility functions for applications in education and have advocated the use of the standard gamble (von Neumann and Morgenstern, 1953) elicitation procedure with the addition of coherence checking using overspecification and a least squares fit. In this procedure utilities are inferred from probability judgements offered by the assessor. This paper describes local and regional coherence procedures which seek utility coherence in successive restricted domains of the parameter space as preludes to overall coherence checking. These procedures and some others are viewed as possible ways of avoiding anchoring and certainty effect biases found in earlier fixed probability methods, and presumably present in current fixed state procedures.
收起
摘要 :
This paper introduces a theoretical framework that describes the importance of affect in guiding judgments and decisions. As used here, affect means the specific quality of goodness or badness (i) experienced as a feeling state (w...
展开
This paper introduces a theoretical framework that describes the importance of affect in guiding judgments and decisions. As used here, affect means the specific quality of goodness or badness (i) experienced as a feeling state (with or without consciousness) and (ii) demarcating a positive or negative quality of a stimulus. Affective responses occur rapidly and automatically note how quickly you sense the feelings associated with the stimulus word treasure or the word hate. We shall argue that reliance on such feelings can be characterized as the affect heuristic. We will trace the development of the affect heuristic across a variety of research paths and discuss some of the important practical implications resulting from ways that this heuristic impacts our daily lives.
收起
摘要 :
To harness modern multicore processors, it is imperative to develop parallel versions of fundamental algorithms. In this paper, we compare different approaches to parallel best-first search in a shared-memory setting. We present a...
展开
To harness modern multicore processors, it is imperative to develop parallel versions of fundamental algorithms. In this paper, we compare different approaches to parallel best-first search in a shared-memory setting. We present a new method, PBNF, that uses abstraction to partition the state space and to detect duplicate states without requiring frequent locking. PBNF allows speculative expansions when necessary to keep threads busy. We identify and fix potential livelock conditions in our approach, proving its correctness using temporal logic. Our approach is general, allowing it to extend easily to suboptimal and anytime heuristic search. In an empirical comparison on STRIPS planning, grid pathfinding, and sliding tile puzzle problems using 8-core machines, we show that A*, weighted A* and Anytime weighted A* implemented using PBNF yield faster search than improved versions of previous parallel search proposals.
收起
摘要 :
We discuss the problem of scheduling tasks that consume uncertain amounts of a resource with known capacity and where the tasks have uncertain utility. In these circumstances, we would like to find schedules that exceed a lower bo...
展开
We discuss the problem of scheduling tasks that consume uncertain amounts of a resource with known capacity and where the tasks have uncertain utility. In these circumstances, we would like to find schedules that exceed a lower bound on the expected utility when executed. We show that the problems are NP- complete, and present some results that characterize the behavior of some simple heuristics over a variety of problem classes.
收起
